package com.gujiangbo.algorithm;

/**
 * 二分法查找
 *
 * @descr 又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置
 * 的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，
 * 则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。
 */
public class BiSection {
    public static void main(String[] args) {
        int[] data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        int index = search(data, 9);
        System.out.println(index);
    }


    /**
     * @param data
     * @param v
     * @return
     */
    private static int search(int[] data, int v) {
        if (data.length == 0) throw new IllegalArgumentException("array length is zero ");
        int start = 0;//开始查找位置
        int mid;//中间值
        int end = data.length;//数组长度
        // 核心点：向左向右查找要根据变化修改start、end的值
        while (start < data.length) {
            mid = (start + end) / 2;
            if (data[mid] == v) {
                // 中间查找
                return mid;
            } else if (data[mid] < v) {
                // 向右查找
                start = mid + 1;
            } else {
                // 向左查找
                end = mid - 1;
            }
        }
        return -1;
    }
}
